package org.usmile.algorithms.leetcode.hard;

import java.util.TreeSet;

/**
 * 220. 存在重复元素 III
 *
 * 给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
 * 如果存在则返回 true，不存在返回 false。
 *
 *
 * 示例 1：
 * 输入：nums = [1,2,3,1], k = 3, t = 0
 * 输出：true
 *
 * 示例 2：
 * 输入：nums = [1,0,1,1], k = 1, t = 2
 * 输出：true
 *
 * 示例 3：
 * 输入：nums = [1,5,9,1,5,9], k = 2, t = 3
 * 输出：false
 *
 * 提示：
 * 0 <= nums.length <= 2 * 104
 * -231 <= nums[i] <= 231 - 1
 * 0 <= k <= 104
 * 0 <= t <= 231 - 1
 */
public class _0220 {
}

class _0220_Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        int left = 0;
        int right = 0;

        TreeSet<Long> window = new TreeSet<>();

        while (right < nums.length) {
            // 窗口内区间查找
            long x = nums[right];
            // 找到大于等于 x - t 的最小的元素 y，确定 y - x <= t
            Long y = window.ceiling(x - (long)valueDiff);
            // 如果 y 存在，并且 y <= x + t，就可以确定  x - y <= t
            if (y != null && y <= x + valueDiff) {
                return true;
            }

            window.add((long)nums[right]);

            if (window.size() > indexDiff) {
                // bug 修复：需要强转成 long 类型
                window.remove((long)nums[left]);
                left++;
            }

            right++;
        }

        return false;
    }
}